/*
 * Copyright (C), 2015-2018
 * FileName: Solution111
 * Author:   zhao
 * Date:     2018/9/9 17:13
 * Description: 111. 二叉树的最小深度
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.diynode.TreeNode;
import com.lizhaoblog.hundredone.CommonValue;

/**
 * 〈一句话功能简述〉<br>
 * 〈111. 二叉树的最小深度〉
 *
 * @author zhao
 * @date 2018/9/9 17:13
 * @since 1.0.1
 */
public class Solution111 {
  /**************************************
   * 题目
   给定一个二叉树，找出其最小深度。

   最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

   说明: 叶子节点是指没有子节点的节点。

   示例:

   给定二叉树 [3,9,20,null,null,15,7],

   3
   / \
   9  20
   /  \
   15   7
   返回它的最小深度  2.
   **************************************/

  /**************************************
   *
   * 想法：
   *    使用104最大深度的递归方案，该max成min
   * 我的做法
   *    超过75.06%的测试案例
   * 总结：
   *    中间还是有问题
   *    逻辑上面还没有理顺
   *    分情况进行判断就好
   * ***********************************/
  public int minDepth(TreeNode root) {
    if (CommonValue.NOT_ANSWER) {
      // 这题看了下其他人的回答才做出来
    }

    if (root == null) {
      return 0;
    }

    return recDepth(root, 1);
  }

  private int recDepth(TreeNode root, int depth) {
    if (root == null) {
      return depth;
    }

    if (root.left == null && root.right == null) {
      return depth;
    }
    depth++;
    if (root.left == null) {
      return recDepth(root.right, depth);
    }
    if (root.right == null) {
      return recDepth(root.left, depth);
    }

    int leftDepth = recDepth(root.left, depth);
    int rightDepth = recDepth(root.right, depth);
    return Math.min(leftDepth, rightDepth);
  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public int better(TreeNode root) {
    if (root == null) {
      return 0;
    }

    if (root.left == null && root.right == null) {
      return 1;
    }

    if (root.left == null) {
      return better(root.right) + 1;
    }

    if (root.right == null) {
      return better(root.left) + 1;
    }

    int lc = better(root.left) + 1;
    int rc = better(root.right) + 1;

    return lc <= rc ? lc : rc;
  }
}
